package com.leetcode.No0795;

import org.junit.Test;

/**
 * @program: Solution
 * @description: 区间子数组个数
 * @author: Wang Zhihua
 * @date: 2022-11-24
 */
public class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int n = nums.length;
        int ans = 0;
        boolean cal = false;
        int subLen = 0;
        int exceptNum = 0;
        for (int num : nums) {
            if (num <= right) {
                ++subLen;
            }
            if (num < left) {
                ++exceptNum;
            }
            if (num >= left && num <= right) {
                cal = true;
            }
            if (cal && num >= left && exceptNum > 0) {
                ans -= calSum(exceptNum);
                exceptNum = 0;
            }
            if (cal && num > right && subLen > 0) {
                ans += calSum(subLen);
                cal = false;
                subLen = 0;
            }
            if (!cal && num > right) {
                subLen = 0;
                exceptNum = 0;
            }
        }
        if (cal && exceptNum > 0) {
            ans -= calSum(exceptNum);
        }
        if (cal && subLen > 0) {
            ans += calSum(subLen);
        }
        return ans;
    }
    
    private int calSum(int x) {
        int y = x + 1;
        if ((x & 1) == 0) {
            x >>= 1;
        } else {
            y >>= 1;
        }
        return x * y;
    }

    @Test
    public void test01() {
        int[] nums;
        int left, right;

        nums = new int[]{2,1,4,3};
        left = 2;
        right = 3;
        System.out.println(numSubarrayBoundedMax(nums, left, right));

        nums = new int[]{2,9,2,5,6};
        left = 2;
        right = 8;
        System.out.println(numSubarrayBoundedMax(nums, left, right));

        nums = new int[]{876,880,482,260,132,421,732,703,795,420,871,445,400,291,358,589,617,202,755,810,227,813,549,791,418,528,835,401,526,584,873,662,13,314,988,101,299,816,833,224,160,852,179,769,646,558,661,808,651,982,878,918,406,551,467,87,139,387,16,531,307,389,939,551,613,36,528,460,404,314,66,111,458,531,944,461,951,419,82,896,467,353,704,905,705,760,61,422,395,298,127,516,153,299,801,341,668,598,98,241};
        left = 658;
        right = 719;
        System.out.println(numSubarrayBoundedMax(nums, left, right));

        nums = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        left = 1;
        right = 10;
        System.out.println(numSubarrayBoundedMax(nums, left, right));

        int n = 50000;
        nums = new int[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = n - i;
        }
        left = 1;
        right = n;
        System.out.println(numSubarrayBoundedMax(nums, left, right));
    }
}
